#include "BinaryTree.h"

// 通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树
BTNode* BinaryTreeCreate(BTDataType* a,int* p)
{
    BTNode* Tree = (BTNode*)malloc(sizeof(BTNode));
    if(a[*p]=='#')
    {
        (*p)++;
        return NULL;
    }
        Tree->_data=a[(*p)++];
        Tree->_left=BinaryTreeCreate(a,p);
        Tree->_right=BinaryTreeCreate(a,p);
    return Tree;
}

// 二叉树销毁
void BinaryTreeDestory(BTNode** root)
{
    if(*root==NULL) return;
    BinaryTreeDestory(&(*root)->_left);//递归到叶子节点再销毁
    BinaryTreeDestory(&(*root)->_right);
    free(*root);
}

// 二叉树节点个数
int BinaryTreeSize(BTNode* root)
{
    //静态变量无法释放 第二次调用函数时会接着往上加
    // static int size=0;
    // if(root==NULL) return 0;
    // ++size;
    // BinaryTreeSize(root->_left);
    // BinaryTreeSize(root->_right);
    // return size;
    if(root==NULL) return 0;
    return BinaryTreeSize(root->_left)+
           BinaryTreeSize(root->_right)+1;
    //return root==NULL? 0:BinaryTreeSize(root->_left)+BinaryTreeSize(root->_right)+1;
    
}

// 二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root)
{   //为NULL时返回0 结束递归
    if(root==NULL) return 0;
    //节点左右都为NULL时是叶子节点
    if(root->_left==NULL&&root->_right==NULL) return 1;

    return BinaryTreeLeafSize(root->_left)
          +BinaryTreeLeafSize(root->_right);
}

// 二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k)
{
    if(root==NULL)
    {
        return 0;
    }
    if(k==1) //当k=1时 是要计算的层数 如果不为NULL则+1
    {
        return 1;
    }
    return BinaryTreeLevelKSize(root->_left,k-1)+
           BinaryTreeLevelKSize(root->_right,k-1);
    /*      A      相对于A层 DEFG层为第三层 k=3
          /   \
         B     C   相对于BC层 DEFG层为第二层 k-1层 也就是k=2
        / \   / \
       D   E  F  G 相当于DEFG层 DEFG层为第一层 k-1-1层 也就是k=1
            \ 
             H
    计算第三层有几个节点时 k-1层B的子节点数+C的子节点数
    当BC的子节点不为NULL时 就能返回k==1 
    k==1 B的左节点不为NULL 返回1 加上 右节点不为NULL 返回1
    那么子树B(k-1层)有2个节点 同理子树C(k-1层)有2个
    递归回去后 k!=1 root!=NULL 则返回 2 + 2 = 3
    */

}

// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
    if(root==NULL) return NULL;
    if(root->_data==x) return root;//递归结束条件
    
    // if(BinaryTreeFind(root->_left,x)) //先遍历左子树 
    
    //     return BinaryTreeFind(root->_left,x);
    
    // else            //左子树找不到再遍历右子树

    //     return BinaryTreeFind(root->_right,x);
    BTNode* left=BinaryTreeFind(root->_left,x);
    BTNode* right=BinaryTreeFind(root->_right,x);
    return left ? left : right; 
}

// 二叉树前序遍历 
void BinaryTreePrevOrder(BTNode* root)
{
    if(root==NULL)
    {
        printf("NULL ");
        return;
    }
    printf("%c ",root->_data);
    BinaryTreePrevOrder(root->_left);
    BinaryTreePrevOrder(root->_right);
}

// 二叉树中序遍历
void BinaryTreeInOrder(BTNode* root)
{
    if(root==NULL)
    {
        printf("NULL ");
        return;
    }
    BinaryTreeInOrder(root->_left);
    printf("%c ",root->_data);
    BinaryTreeInOrder(root->_right);
}

// 二叉树后序遍历
void BinaryTreePostOrder(BTNode* root)
{
    if(root==NULL)
    {
        printf("NULL ");
        return;
    }
    BinaryTreePostOrder(root->_left);
    BinaryTreePostOrder(root->_right);
    printf("%c ",root->_data);
}

// 层序遍历
void BinaryTreeLevelOrder(BTNode* root)
{
    /*用队列遍历 当树不为空时，先入列头节点A 然后出列A保存，打印A，再判断
      A的左节点是否为空，不为空则入列 B，再判断右节点 C，不为空入列。每次
      只出列一个节点，当遍历到所有叶子节点时左右都为空，没节点入列，队列也
      出完了，结束循环。
    
          A
         / \
        B   C
       / \
      D   E*/
    Queue q;
    QueueInit(&q);
    if(root!=NULL)  QueuePush(&q,root);//树不为空 插入根节点
    while(!QueueEmpty(&q))//为空
    {
        QDataType front = QueueFront(&q);//BTNode*=QDataType
            printf("%c ",front->_data);
            QueuePop(&q);//出列
        if(front->_left!=NULL)
        {
            QueuePush(&q,front->_left);//左子节点不为空则入列
        }
        if(front->_right!=NULL)
        {
            QueuePush(&q,front->_right);//右子节点不为空则入列
        }
    }
    printf("\n");
    QueueDestroy(&q);
}

// 判断二叉树是否是完全二叉树
// 完全二叉树的层序应该是 A B C D E F G H NULL NULL NULL... 后面没有节点了
int BinaryTreeComplete(BTNode* root)
{
    Queue q;
    QueueInit(&q);
    if(root!=NULL)  QueuePush(&q,root);//树不为空 插入根节点
    while(!QueueEmpty(&q))//为空
    {
        QDataType front = QueueFront(&q);//BTNode*=QDataType
        if(front==NULL) break; //如果是完全二叉树的话NULL后面不应该有节点，所以退出循环
            QueuePop(&q);//出列
    
            QueuePush(&q,front->_left);//左子节点入列

            QueuePush(&q,front->_right);//右子节点入列
    }
    while(!QueueEmpty(&q))//开始判断后面是否全NULL
    {
        QDataType front = QueueFront(&q);
        if(front !=NULL) 
        {
            QueueDestroy(&q);   
            return 0; //边入边出，不为全NULL那就是不完全二叉树
        }
        
        
       
        QueuePop(&q);
    }
    QueueDestroy(&q);
    return 1;
}